//https://leetcode.cn/problems/verify-preorder-serialization-of-a-binary-tree/description/?envType=daily-question&envId=2024-03-31


class Solution {
public:
    bool isValidSerialization(string preorder) {
        int n = preorder.size();
        int outdegree = 1; // 初始为1，表示根节点的出度
        for (int i = 0; i < n; ++i) 
        {
            if (preorder[i] == ',') continue; // 忽略逗号
            else if (preorder[i] == '#') --outdegree; // 空节点，出度减一
            else 
            {
                ++outdegree; // 非空节点，出度加一
                while (i < n && preorder[i] != ',') ++i;
            }
            if (outdegree == 0 && i < n - 1) 
            {
                // 如果出度为0但未遍历完整个序列，则返回false
                return false;
            }
        }
        // 最后检查出度是否为0，且已经遍历到序列末尾
        return !outdegree;
    }
};
